/***************************************
定义：
    dp[i]: 整齐打印第i到第n-1个单词的行尾额外空格数立方之和的最小值。
    rl[i]: sigma(k=i->n-1)W[i]+(n-1-i), 第i到n-1个单词间隔一个空格排列的总长度。
    W[i]: 第i个单词的长度
    n: 单词总数
    ML: 单行最大长度
初始化：
     rl[n-1]=W[n-1];
递推：
    rl[i] = {
        W[i]+1+r[i+1], i<n-1
    }
    dp[i] = {
        0, rl[i]<ML
        min{m3d(ML-(rl[j]-rl[i]))+dj[j]|i<=j<n && rl[j]-rl[i]<M}    
    }
    
***************************************/
#include <climits>
#include <vector>
#include <algorithm>
#include <stdio.h>


using std::min;
using std::vector;

typedef vector<int> IV; 
class NPrint {
public:
    int ML; //行长度
    IV const &W; //单词长度向量
public:
    NPrint(IV const &W, int ML): W(W), ML(ML) {} 
    long neatly_print(void);
private:
    vector<long> dp;
    long m3d(int n) { return n*n*n; } 
    
};


long NPrint::neatly_print(void) {
    int wc = W.size();
    dp.resize(wc);
    dp[wc-1] = 0;
    int len = dp[wc-1];
    int i;
    for(i=wc-2; i>=0; i--) {
        len += W[i]+1;
        if(len>ML) break;
        dp[i] = 0;
    }
    while(i>=0) {
        int j = i+1;
        int len = W[i];
        dp[i] = LONG_MAX;
        do {
            dp[i] = min(dp[i], m3d(ML-len)+dp[j]);
            len += W[j++]+1;
        }while(len<ML);
        i--;
    }
    return dp[0];
}

int main(void) {
    IV W {3, 10, 7, 6, 8, 10, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 6, 6, 6, 6, 6, 6, 7, 8, 9, 1, 1, 1, 1};
    NPrint np(W, 100);
    printf("NP: %ld\n", np.neatly_print());
    return 0;
}
